package m202405.d25;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/25 15:27
 */
public class Q207 {

    public static void main(String[] args) {
        Q207 q207 = new Q207();
        boolean b = q207.canFinish(3, new int[][]{
                {0, 1},
                {0, 2},
                {1, 2}
        });
        System.out.println();
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
            Set<Integer> set = map.getOrDefault(prerequisite[0], new HashSet<>());
            set.add(prerequisite[1]);
            map.put(prerequisite[0], set);
        }

        int[] flag = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            find(flag, new boolean[numCourses], map, i);
            if (flag[i] == -1) {
                return false;
            }
        }
        return true;
    }

    public void find(int[] flag, boolean[] visited, Map<Integer, Set<Integer>> map, int i) {
        if (visited[i]) {
            flag[i] = -1;
            return;
        }
        visited[i] = true;
        if (flag[i] == 0) {
            Set<Integer> set = map.get(i);
            if (set == null) {
                flag[i] = 1;
                return;
            }
            for (Integer j : set) {
                if(flag[j]==0){
                    find(flag, visited, map, j);
                }
                if (flag[j] == -1) {
                    flag[i] = -1;
                    return;
                }
            }
            flag[i] = 1;
        }
    }
}
